/**
 * 1737. 满足三条件之一需改变的最少字符数
 * https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/
 */
public class Solutions_1737 {
    public static void main(String[] args) {
//        String a = "aba", b = "caa";  // output: 2
//        String a = "dabadd", b = "cda";  // output: 3
        String a = "azzzz", b = "bzzzz";  // output: 2

        int result = minCharacters(a, b);
        System.out.println(result);
    }

    /**
     * 解题思路：
     * 通过循环 25 个英文字母，分别计算出当前字母下，要使 a，b 满足 3 个条件时，共需要的操作数
     */
    public static int minCharacters(String a, String b) {
        int[] aMap = new int[26];
        int[] bMap = new int[26];
        char[] arrA = a.toCharArray();
        char[] arrB = b.toCharArray();
        int len1 = a.length(), len2 = b.length();

        // 记录出现的次数
        for (char c : arrA) {
            aMap[c - 'a'] ++;
        }
        for (char c : arrB) {
            bMap[c - 'a'] ++;
        }
        int res = len1 + len2;

        // 记录已经出现的字母个数
        int aCnt = 0, bCnt = 0;
        // 不用遍历到 z，因为判断条件为一方小于等于 'y'，一方就是大于 'y' 了，即 'z'
        for (int i = 0; i < 25; i++) {
            aCnt += aMap[i];
            bCnt += bMap[i];

            // 1、使 a 中字符全部小于等于 i：a 的长度 - 小于等于 i 的个数（aCnt）
            //   而 b 中字符全部大于 i：小于等于 i 的个数（bCnt）
            int change1 = len1 - aCnt + bCnt;
            res = Math.min(res, change1);

            // 2、使 a 中字符全部大于 i：小于等于 i 的个数（aCnt）
            //   而 b 中字符全部小于等于 i：b 的长度 - 小于等于 i 的个数（bCnt）
            int change2 = len2 - bCnt + aCnt;
            res = Math.min(res, change2);

            // 3、使 a，b 字符都等于 i：a 的长度 + b 的长度 - a 中 i 出现的次数 - b 中 i 出现的次数
            int change3 = len1 + len2 - aMap[i] - bMap[i];
            res = Math.min(res, change3);
        }
        // for 循环中没有进行都转换为 z 的操作
        int change = len1 + len2 - aMap['z' - 'a'] - bMap['z' - 'a'];
        res = Math.min(res, change);
        return res;
    }
}
